The operation of a system—general term used in this description and in the attached claims to represent industrial plants, manufacturing or research equipment, various types of vehicles (e.g. aircraft or spacecraft)—is controlled usually by means of complex diagnostic systems able to detect and isolate abnormal operating conditions as soon as they occur. In ground-controlled space missions, either in Earth orbit or in deep space, prominent attention is devoted to the diagnosis of the system formed by the spacecraft and its onboard equipment, and in particular to the real-time detection of system faults, to correct the malfunctions which might compromise the mission.
The basic principle of model-based diagnostics is the comparison between the expected or nominal behaviour of a system, provided by a model of the system, and the actual behaviour inferred from measurements on the system, acquired by means of a set of sensors associated to said system.
In general, the model-based diagnostics of a system includes three phases:                Fault detection: given a specific set of inputs to the system and its model, a system simulation is carried out to compute the expected sensor readings. Any discrepancy or inconsistency between sensors expected readings and their actual values indicates a fault. This phase essentially consists in determining whether inconsistencies occur between expected and observed sensor measurements;        Generation of the sets of conflicts: in this phase, given the inconsistencies between expected and actual sensor readings, a large number of sets of conflicts is generated, each of them implying that at least one of its components is faulty, due to the observed inconsistencies;        Diagnosis: in this phase, given the sets of conflicts, the system is diagnosed, i.e. the minimum number of faults is determined. This phase is carried out solving problems of determining a hitting set, which determine the minimum number of components intersection of all the sets of conflicts, starting from the given sets of conflicts. This minimum set represents the set of faulty components originating the observed inconsistencies, and therefore represents eventually the diagnosis of the system.        
The first phase of fault detection is immediate and requires only a simulation of the system. The third phase was for a long time a limitation to an efficient diagnosis, but recently a logical-mathematical tool has been developed which allows a rapid solution to the problem of determining a hitting set, even for complex systems. The current obstacle to a rapid system diagnosis is the lack of efficiency in the phase of generating the sets of conflicts.
Presently there are two classes of methodologies and different approaches to derive sets of conflicts.
In the last few decades, research in the field of system diagnostics, based on a model describing the functions of the system components and its connectivity or topology, has been carried out essentially according to two different paths:
one, the approach of Fault Detection and Isolation (FDI), exploits the complete knowledge of the system and is based on automatic control theories and statistical decisions; the other, known as DX approach, does not need the complete knowledge of the system and is based on Artificial Intelligence techniques applied to a set of assumptions on the modes of operation of the system as a whole.
The FDI approach uses for its application the Analytical Redundancy Relations (ARRs), also known as residuals or parity equations, each of them representing a different relation between measured parameters of the system. Each unsatisfied ARR indicates a discrepancy between the expected system behaviour and the actual one, and allows the detection of a system malfunction, due to some fault, compared to normal operation.
The DX approach is based instead on the concept of conflict, and more generally of conflict set, which is a set of system components, for which the assumption of correct operation is not consistent with the observed system behaviour.
Recently, a unified picture of the two mentioned theories has shown their fundamental equivalence. The relation between the concepts of analytical redundancy relation and of conflict has been recognized in the fact that the support of an ARR, i.e. the set of components involved in that ARR, is a possible conflict, i.e. a possible scenario of measurements on the system exists, which generates that set as a conflict.
Both approaches, individually adopted to carry out the diagnostics of a system, exhibit significant computational disadvantages, which make them inefficient for many interesting applications.
As far as the approach based on the ARRs is concerned, the known algorithms for the generation of a complete set of ARRs exhibit an exponential computation complexity, so that the generation and application of ARRs for real cases turn out to be practically impossible.
Moreover, for many practical systems of interest, the set of ARRs may not be obtainable in analytical form, thus preventing its actual use.
On the other hand, in the DX approach, the most commonly used General Diagnosis Engine (GDE) algorithm requires performing many consistency checks between expected values from the model and observed values on the system, while many of said checks might turn out not being strictly necessary for the diagnosis result, thus its application as well leads to an exponential computational complexity.
The DX and FDI Approaches
In the following a deeper discussion of the approaches to system diagnostics according to the known DX and FDI techniques is provided, aimed to clarify and explain the developments of the invention.
In model-based diagnostics, the models of the devices forming a complex system are compared to the observations of the actual behaviour of the system to detect possible discrepancies (inconsistencies) and to diagnose the originating causes (faults).
A System Model (SM) consist of a Behavioral Model (BM) and of an Observation Model (OM). The behavioral model BM is a description of the system based on its components and consists of a set of Primary Relations (PR). Each component is described by the function it performs, i.e. by one or more primary relations PR and by its inputs and outputs, so that the components-based description includes the system topology as well. The observation model OM is the set of relations defining the observations carried out on the system by means of a plurality of sensors associated to it.
FIG. 1 shows the example of a multiport system, consisting of three multipliers (M1, M2, M3) and two adders (A1, A2).
The behavioral model of this system, which provides its description in terms of components and topology, is given by a set of Primary Relations PR and by the components associated to them, as defined by the following:                PR1: x=a c; M1         PR2: y=b d; M2         PR3: z=c e; M3         PR4: f=x+y; A1         PR5: g=y+z; A2         
The DX Approach
From the point of view of the DX approach, each PR is modelled as a set of rules to propagate the values from a variable to another variable.
For example, the component multiplier M1 is defined by the following three rules, which assume the condition that M1 operates correctly.                1) x=ac        2) if (a≠0) then c=x/a        3) if (c≠0) then a=x/c        
Notice that while the first rule infers an output given the inputs, the other two determine conditionally an input, given the output and the other input.
In fact, the DX approach allows each variable to take a set of possible values given different assumptions, and taking into account each value together with the use of the relevant rules allows the computation of the values of other system variables. As these computations are based on initial assumptions, a DX algorithm tags each value assigned to a variable with the assumptions leading to its computation (tagged value).
Therefore, the above mentioned rules actually translate into the following ones, where Sv is the set of values which can be associated to the variable v, and <n:N>εSv means that v=n (i.e. the variable v takes the value n) when the set of assumptions N is fulfilled.
<n:N>εSa<m:M>εSc<nm:N∪M∪{M1}>εSx<n:N>εSa<m:M>εSxn≠0<m÷n:N∪M∪{M1}>εSc<n:N>εSc<m:M>εSxn≠0<m÷n:N∪M∪{M1}>ÅSa 
For example, setting the inputs a=2 and c=2 determines the addition of <2:{ }> in Sa and of <2:{ }> in Sc, which leads the DX algorithm to infer that <3:{M1}>εSx, which triggers further inferences adding an element to the set Sx.
A discrepancy or inconsistency arises during the inferential propagation of values between the system variables, from the inputs to the outputs, when two different values are assigned to the same variable.
For example, setting all the inputs of the multiport system in FIG. 1 to “2” determines by inference <8:{M2,M3,A2}>εSg.
A later measurement g=9 determines a discrepancy because <9:{ }> is also an element of Sg due to the measurement, but is not consistent with the system model. The union of the assumptions contributing to this result leads to the detection of a discrepancy, which implies that M2, M3, or A2 must be a faulty component.
Typically, in the course of an inferential propagation of values within a system no discrepancies are found, but when faults occur in a system a plurality of discrepancies may show up. In fact the process of causal inference continues to determine new discrepancies until the propagation of the possible tagged values of the variables at the output of the system is completed; this may require a very long time, as the number of values assigned to each variable may grow exponentially with the number of possible assumptions. This leads a generic DX algorithm to require an exponential time to propagate the values in the whole system.
Next, the generic DX algorithm finds the minimal sets of assumptions intersection of all the detected discrepancies, which represent the diagnosis of the causes of the contradictory measurements.
Unfortunately, the computation of the minimum set has equivalent complexity to the problem of computing the prime implicants, which is a NP-complete problem.
For improved performance, the DX algorithm GDE (General Diagnosis Engine) uses a minimalist approach to the management of the sets, eliminating <n:Li> from a set if <n:Lj> belongs to the set and Lj⊂Li. This is possible because the second element makes <n:Li> redundant when a value is determined on the basis of the starting assumptions.
The set of discrepancies is further minimized by eliminating a redundant discrepancy Li when another discrepancy Lj exists such that Lj⊂Li. Such tests on subsets reduce the computational loads of the inferential process, but also imply that the test procedure is called many times in the algorithm, and this anyway requires a long computing time.
In the end, the diagnostic model according to the DX approach results in a system in which each variable can be tested. However, the goal would be to test the smallest possible number of variables. Actually, a DX algorithm is able to identify a number of possible diagnoses of a discrepancy and to suggest the measurement of a determined subset of variables to reduce the ambiguity of the diagnosis.
Although this approach is theoretically advantageous, in practice one realizes that some variables cannot be measured when the system of interest is in a remote location or unreachable (e.g. in the case of spacecraft traveling in deep space). The DX approach must therefore be applied by defining in advance the actually measurable variables, i.e. the sensors associated to the system which allow its observation. The problem therefore arises to identify a priori the most suitable variables to be measured, to minimize the ambiguities of the diagnosis.
The FDI Approach
The main feature wherein the FDI approach differs from the DX approach is the initial assumption that the observation sensors are defined a priori.
The optimization of sensors and the diagnostic technique are based on the concepts of Analytical Redundancy Relation (ARR) and Fault Signature Matrix (FSM).
In the following the concepts of ARR and FSM are introduced and briefly discussed, for the sake of clarity and simplicity considering the case of single fault only in a system.
The set of variables (V) in a system, for example the system shown in FIG. 1, can be decomposed into a set of unknown variables (X) and a set of observed variables (O), i.e. the relation V=X∪UO holds.
An Analytical Redundancy Relation (ARR) is a constraint deduced from the system model (SM). The ARRs can be deduced from the SM by elimination of the unknown variables from the Primary Relations (PR). Therefore an ARR contains observed variables only, hence it can be computed from them.
The support of an ARR is the subset of components involved in the derivation of said ARR.
For the system shown in FIG. 1, if the sensors are deployed at outputs f and g, and the inputs a, b, c, d, e are known, then O={a, b, c, d, e, f, g} and X={x, y, z}.
The resulting ARRs are listed in the following Table 1:
TABLE 1ARRs, support components and sensors for the example in FIG. 1ARRSupport componentsSensorsARR1: f = ac + bdM1, M2, A1fARR2: g = bd + ceM2, M3, A2gARR3: f − g = ac − ceM1, M3, A2, A1f, g
The ARRs are then used to check the consistency of the observations on the system against the SM. In other words, the ARRs are satisfied if the observed system behaviour satisfies the model constraints, i.e provides observations expected from the model.
Under the assumption of a single fault, i.e. if one component only of the support of an ARR is faulty, then that ARR is not satisfied.
In fact, together with the concept of support set, this statement is the basis of the approach of model-based diagnostics within the FDI methodology.
A Fault Signature Matrix (FSM) can be deduced from the ARRs. The FSM is defined as a binary matrix whose rows are the ARRs generated for the system under study and whose columns represent the system components.
An element FSij of this matrix equals 1 if the associated system component Ci belongs to the support of relation ARRj, otherwise FSij=0. The i-th column corresponding to component Ci is defined as Fault Signature Vector (FSV) of Ci and is called FSVi=[FSVi1, . . . , FSVin]t.
Referring to the system depicted in FIG. 1, the FSM can be deduced from Table 1 and is shown in the following Table 2.
TABLE 2Fault Signature Matrix for the system shown in FIG. 1A1A2M1M2M3ARR110110ARR201011ARR311101
The case of multiple faults can be dealt with by expanding the columns of the FSM. The multiple fault signature vector FSV can be obtained from the single fault signature vectors FSVk occurring simultaneously, by carrying out a logical OR operation between corresponding elements of the corresponding FSVk. Therefore, in a system having n components, taking into account all the possible combinations of multiple faults leads to the generation of a FSM having 2n columns.
The system diagnostics is therefore based on the evaluation of the ARRs, starting from a set of observations on the system.
If an ARRi is satisfied on the basis of the observations, then ARRi=0, otherwise ARRi=1. The ARRs are instantiated with the observed values, providing an observed signature. The signature of the i-th observation is defined as a binary vector OSi=[OSi1, . . . , OSin]t, where OSij=0 if ARRj is satisfied by the observations, and OSij=1 otherwise.
Table 3 shows the diagnosis of the system shown in FIG. 1, on the basis of different observation signatures.
TABLE 3Diagnosis of the system depicted in FIG. 1, for different observation signatures.DiagnosisObservationsARR100111ARR201011ARR301101Single moneA2; M3A1; M1M2nonefaultdiagnosisMultiplenone(A2, M3)(A1, M1)noneAll the sets offaultdouble faults,diagnosis(A1, M1) and(A2, M3) ex-cluded
The diagnosis is given on the basis of the faults taken into account in the FSM, i.e. an observed signature OSi=[OSi1, . . . , OSin]t is consistent with a fault signature FSi=[FSi1, . . . , FSin]t if FSij=OSij for each j.
For example, for the system in FIG. 1 the OS=[0,1,1]t is equivalent to the fault signature of components A2 and M3.
Notice that this shows that, depending on the system sensors, the faults of components A2 and M3 cannot be discriminated, as in the case of A1 and M1.
The criterion of detection and isolation (fault discrimination) can be described in terms of FSM.
All faults can be detected (complete detection) if there is no null column (i.e. no FSV with all zero elements) in the FSM. That is, for a given faulty component Ci, at least one ARR is affected. Fault isolation is guaranteed if there are no two identical columns in the FSM, since this fact would imply that the two FSVs are identical and therefore the corresponding faults cannot be discriminated.
The biggest obstacle in the use of the ARRs for a diagnostic procedure comes from the efficient generation of the complete, non-redundant set of ARRs, which is at present a limitation of the available algorithms for the execution of diagnoses according to the FDI approach.
A first feature to be taken into account is the possible number of ARRs.
Let's consider a system described by n primary relations (PR) (typically this means that the system has n components, but in general this might imply that the system has at most n components) and m sensors (observations), where n>m in most realistic cases.
If the ARRs are considered as functions of all possible combinations of observations, then the total number of ARRs would be of the order of O(2m). On the other hand, if we consider that the ARRs are derived from the combination of PRs by eliminating the unknown variables, this implies an upper bound to the number of ARRs of the order of O(2n).
The key point, which the inventors believe has not been sufficiently appreciated in the currently used techniques, is the fact that the ARRs may involve all the possible combinations of PRs and observations.
Actually, the same set of PRs can lead to different ARRs, i.e. to different ARRs having the same support set, but different sets of observations.
Cases may also occur, wherein the same set of observations can lead to different ARRs, which differ in their support components.
Taking this view, we can therefore conclude that the upper bound to the total number of ARRs is actually of the order of O(2n+m). Of course, for any realistic system the number of ARRs is always finite, due to the structural constraints of the system.
Another fundamental question in the application of the ARRs, both for system diagnostics and for the problem of sensor optimization, is related to the completeness of the set of ARRs. More precisely, the inventors are aware of the fact that the problem of the minimum complete set of ARRs has not attracted so far sufficient attention.
In the literature the concepts of d-completeness (completeness as to fault detection) and i-completeness (completeness as to fault isolation) have been discussed. However, these two concepts can be used only for the applicability analysis of a given set of ARRs for the diagnosis of a system, while the problem of generating a complete set of ARRs is not directly faced; on the other hand it is obvious that completeness is a fundamental issue both for diagnostics and for sensors optimization, since the highest possible information from the ARRs is required for both problems.
It is also obvious that any application of an incomplete set of ARRs, both for system diagnostics and for optimization of sensors associated to said system, may lead to wrong or suboptimal results.
The inventors, in their article “A new efficient method for system structural analysis and generating analytical redundancy relations”, Proc. IEEE Aerospace Conference, March 2009, have presented an innovative method for the generation of a complete set of ARRs, whose complexity is only O(L4), even in the worst case, where L is the number of relations in the system; this method solves some limitations of the ARR generation algorithms known before, disadvantageously non-deterministic and exhibiting exponential complexity.
Another issue to be considered is that, although the complexity of computing the ARRs is specific for each system, a common disadvantage of this technique is the fact that the evaluation of all the ARRs is required to diagnose the system; this implies heavy computation loads even if there is no fault in the system. In other words, it is not possible to determine a priori a subset of ARRs whose computation is sufficient to respond to the specific diagnostic needs.
Another issue to be considered is the actual feasibility of the computation (evaluation) of the ARRs. As an ARR is by definition generated by combining a set of PRs, such combination may require the inversion of the functions representing one or more PRs, expressed in analytical form. As a matter of fact, in real systems encountered in practical applications, the functions representing primary relations of some non-linear components cannot be inverted in analytical form, but can only be expressed numerically: this poses a further major obstacle, increasing the computational load of the procedure and limiting its practical applicability.
Finally, as above mentioned, after evaluating the ARRs and forming the observation or observed signature vector, the latter must be compared to the fault vectors in FSM. Although this operation is rather simple, its complexity is increased in case of multiple fault diagnosis.
If we consider a system having n components and all possible combinations of faults, then a FSM having 2n columns would be generated: this leads to an exponential growth of the memory space to be allocated to the FSM in the computing system for the execution of the diagnostic algorithm, and in the computing time required by said system to carry out the comparison of the observation vector against the fault vectors.